# 给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
#  选择二叉树中 任意 节点和一个方向（左或者右）。
#  如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
#  改变前进方向：左变右或者右变左。
#  重复第二步和第三步，直到你在树中无法继续移动。
#  交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
#
#  请你返回给定树中最长 交错路径 的长度。
#  示例 1：
#  输入：root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
# 输出：3
# 解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。
#
#  示例 2：
#  输入：root = [1,1,1,null,1,null,null,1,1,null,1]
# 输出：4
# 解释：蓝色节点为树中最长交错路径（左 -> 右 -> 左 -> 右）。
#
#  示例 3：
#  输入：root = [1]
# 输出：0
from com.example.tree.tree_node import TreeNode


class Solution:
    def longestZigZag(self, root: TreeNode) -> int:
        """
        endLeft, endRight = dfs(node) 代表状态如下：
            endLeft表示以node节点为结尾的以左向为停止的交错路径的长度
            endRight表示以node节点为结尾的以右向为停止的交错路径的长度
        使用res表示最终结果，每算完一个节点的结果，尝试更新res
        :param root:
        :return:
        """
        res = 0

        def dfs(node: TreeNode) -> list:
            if not node:
                return [0, 0]
            leftRes = dfs(node.left)  # endLeft endRight
            rightRes = dfs(node.right)
            if node.left:
                leftRes[1] += 1
            if node.right:
                rightRes[0] += 1
            nonlocal res
            res = max(res, max(leftRes), max(rightRes))
            return [leftRes[1], rightRes[0]]
        dfs(root)
        return res


if __name__ == "__main__":
    #    1
    #        1
    #     1      1
    #          1    1
    #            1
    #              1
    # root = TreeNode(1)
    # root.right = TreeNode(1)
    # root.right.left, root.right.right = TreeNode(1), TreeNode(1)
    # root.right.right.left, root.right.right.right = TreeNode(1), TreeNode(1)
    # root.right.right.left.right = TreeNode(1)
    # root.right.right.left.right.right = TreeNode(1)
    #         1
    #    1          1
    #        1
    #     1     1
    #       1
    root = TreeNode(1)
    root.left, root.right = TreeNode(1), TreeNode(1)
    root.left.right = TreeNode(1)
    root.left.right.left, root.left.right.right = TreeNode(1), TreeNode(1)
    root.left.right.left.right = TreeNode(1)
    print(Solution().longestZigZag(root))
